1740E - Hanging Hearts - CodeForces Solution

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>
#include<cmath>

using namespace std;

#define endl "\n"
#define ain(a) for(int _i=0;_i<a.size();_i++) cin >> a[_i]
#define aout(a) for(int _i=0;_i<a.size();_i++) { if(_i > 0) cout << " "; cout << a[_i]; }; cout << endl
#define couty cout << "YES\n"
#define coutn cout << "NO\n"

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()

#ifdef LOCAL_JUDGE
#include "local.hpp"
#else
template <typename Head, typename... Tail> void dout(Head&& h, Tail&&... t) {}
#endif

typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef tuple<ll,int,int> tllii;
typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; typedef vector<vector<int> > vvi; typedef vector<string> vs;

const ll MOD = 1e9+7;

void solve() {
	int n; cin >> n;
	vi a(n);
	for(int i=1;i<n;i++) {
		int pi;
		cin >> pi; pi--;
		a[i] = pi;
	}
	vi c(n);
	vi h(n);
	vi dp(n);
	vb multi(n);
	for(int i=n-1;i>=0;i--) {
		int pi = a[i];
		if(c[i] == 0) {
			dp[i] = 1;
			h[i] = 1;
		} else {
			dp[i] = max(dp[i],h[i]);
		}
		if(i == 0) break;
		c[pi]++;
		dp[pi] += dp[i];
		h[pi] = max(h[pi],h[i]+1);
		multi[pi] = multi[pi] || multi[i];
	}
	// dout(d);
	cout << dp[0] << endl;
}

int main(int argc,char *argv[]) {
#ifdef LOCAL_JUDGE
	freopen(argc > 1 ? argv[1] : "in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	// cin >> t;
	for(int i=1;i<=t;i++) {
		dout("***",i);
		solve();
	}
}